Memory caches are storage systems incorporated into data processing systems for performance reasons. A memory cache stores a subset of the contents of the data processing system's main memory for use by a selected subsystem, typically the system's data processor. A memory cache can supply data to the data processor faster than the main memory can because of several reasons. First, the memory cache is often made of higher grade memory circuits than is the main memory system. These circuits can operate at a higher clock rate than can the main memory. Also, there may be a dedicated bus between the data processor and the memory cache that results in higher bandwidth between the data processor and the memory cache than between the data processor and the main memory. Finally, a memory cache may be physically located on the same integrated circuit as the subsystem to which it provides data. In this case, the memory cache is constructed from faster circuits and there is a dedicated bus between the memory cache and the data processor.
Associativity is one variable that defines memory cache designs. Associativity describes the number of memory cache locations to which each main memory subsystem location may be mapped. For instance, the contents of each main memory location may be mapped to one of two different locations in a two-way set associative memory cache. When the data processor requests the contents of a certain main memory location, the data processor compares the contents of a tag associated with each of the two possible storage locations to a portion of the address of the requested data. The tag is stored in a random access memory ("RAM") associated with each memory cache entry or "cache line." One or none of the tags will match the address portion depending upon the prior history of the data processor. If one of the tags matches, then the associated memory cache location contains the requested data, a cache "hit." If neither of the tags matches, then no memory cache location contains the requested data, a cache "miss."
The selection of the degree of associativity of a cache is a compromise between a desired "hit rate" of the cache or its performance, the minimum cache access time, and the maximum allowable cache complexity. The higher the degree of associativity of a cache, the greater the number of eligible locations in which to store any particular cache line. The greater the number of eligible locations, the more selective the replacement algorithm. Selective replacement algorithms are able to keep desirable cache lines in the memory cache for a longer period of time relative to less desirable cache lines. Therefore, the higher the associativity of a memory cache, the greater the probability of a cache hit. Unfortunately, as the associativity of a memory cache grows, so grows the number of parallel look-ups into the cache necessary to extract the tag information. Also, as the associativity grows, so grows the number of address-tag comparisons necessary to determine if the cache line is present in the memory cache. These characteristics increase the complexity and access time of the cache beyond a simple block of RAM.
The decreased speed and increased complexity of an associative cache may be especially critical if the cache is external to the circuit which requests the cache line; i.e. not an integrated cache. The access time of a non-integrated cache is already degraded by the inherent performance of chip-to-chip data transfers. Also, specialized interface circuits increase the cost and reduce the development time of systems in which they are incorporated.